home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / modelers / linkedit / linkedit.lha / link-edit / LinkEdit / Link / link_private.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-03-13  |  21.5 KB  |  812 lines
  1. #include <stdio.h>
  2. #include <X11/Xlib.h>
  3. #include "link_types.h"
  4. #include "link_global.h"
  5.  
  6.  
  7. LinkComputeDeviceCoords(gnrc)
  8.  
  9. LinkStatus *gnrc;
  10.  
  11. {
  12.   LinkList *lnk;
  13.   LinkPointList *pnt;
  14.   LinkCrossingList *crssng;
  15.   int x_orig,y_orig;
  16.  
  17.   x_orig = gnrc->origin.dcx; y_orig = gnrc->origin.dcy;
  18.   lnk = gnrc->link.next;
  19.   while(lnk != NULL) {
  20.      pnt = lnk->point.next;
  21.      while(pnt != NULL) {
  22.         pnt->dcx = x_orig + (int) (pnt->x * gnrc->xscale * xppmm);
  23.         pnt->dcy = y_orig - (int) (pnt->y * gnrc->yscale * yppmm);
  24.         crssng = pnt->crossing.next;
  25.         while(crssng != NULL) {
  26.            crssng->dcx = x_orig + (int) (crssng->x * gnrc->xscale * xppmm);
  27.            crssng->dcy = y_orig - (int) (crssng->y * gnrc->yscale * yppmm);
  28.            crssng = crssng->next;
  29.           }
  30.         pnt = pnt->next;
  31.        }
  32.      lnk = lnk->next;
  33.     }
  34. }
  35.  
  36. LinkComputePointWorldCoords(gnrc,pnt)
  37.  
  38. LinkStatus *gnrc;
  39. LinkPointList *pnt;
  40.  
  41. {
  42.   pnt->x = (double) (pnt->dcx - gnrc->origin.dcx) /
  43.                      (gnrc->xscale * xppmm); 
  44.   pnt->y = (double) (gnrc->origin.dcy - pnt->dcy) /
  45.                      (gnrc->yscale * yppmm); 
  46.  
  47. }
  48.  
  49. LinkComputePointDeviceCoords(gnrc,pnt)
  50.  
  51. LinkStatus *gnrc;
  52. LinkPointList *pnt;
  53.  
  54. {
  55.    pnt->dcx = gnrc->origin.dcx + (int) (pnt->x * gnrc->xscale * xppmm);
  56.    pnt->dcy = gnrc->origin.dcy - (int) (pnt->y * gnrc->yscale * yppmm);
  57.  
  58. }
  59.  
  60. LinkCrossingList *LinkFindCrossing(gnrc,x,y)
  61. LinkStatus *gnrc;
  62. int x,y;
  63. /* Routine checks all crossings of all links */
  64. {
  65.   LinkList *lnk;
  66.   LinkPointList *pnt;
  67.   LinkCrossingList *rtn,*crssng;
  68.   int x_diff,y_diff,dcx,dcy;
  69.   int xtemp,ytemp;
  70.  
  71.   rtn = NULL;
  72.   lnk = gnrc->link.next;
  73.   while(lnk != NULL) {
  74.      pnt = lnk->point.next;
  75.      x_diff = LINK_X_HIT_RADIUS; y_diff = LINK_Y_HIT_RADIUS;
  76.  
  77.      while(pnt != NULL) {
  78.         crssng = pnt->crossing.next;
  79.         while(crssng != NULL) {
  80.            dcx = crssng->dcx; dcy = crssng->dcy;
  81.            xtemp = (x > dcx) ? x-dcx:dcx-x; ytemp = (y > dcy) ? y-dcy:dcy-y;
  82.            if(xtemp <= x_diff && ytemp <= y_diff) {
  83.               rtn = crssng; x_diff = xtemp; y_diff = ytemp;
  84.              }
  85.            crssng = crssng->next;
  86.           }
  87.         pnt = pnt->next;
  88.        }
  89.      lnk = lnk->next;
  90.     }
  91.   return(rtn);
  92. }
  93.  
  94. LinkList *LinkFindLink(gnrc,x,y)
  95. LinkStatus *gnrc; int x,y;
  96. {
  97.   LinkList *lnk;
  98.  
  99.   lnk = gnrc->link.next;
  100.   while(lnk != NULL) {
  101.      if(LinkFindPoint(gnrc,lnk,x,y) != NULL) break;
  102.      if(LinkFindEdge(gnrc,lnk,x,y) != NULL) break;
  103.      lnk = lnk->next;
  104.     }
  105.   return(lnk);
  106. }
  107.  
  108. LinkPointList *LinkFindEdge(gnrc,lnk,x,y)
  109.  
  110. LinkStatus *gnrc;
  111. LinkList *lnk;
  112. int x,y;
  113.  
  114. /* Returns point representing start of selected edge */
  115.  
  116. {
  117.   int x_diff,y_diff;
  118.   int xtemp,ytemp;
  119.   float t;           /* Line parameter */
  120.   int d,r0,s0,r1,s1;
  121.   LinkPointList *pnt,*selected_pnt;
  122.  
  123.   x_diff = LINK_X_HIT_RADIUS; /* Initialize to just too far away */
  124.   y_diff = LINK_Y_HIT_RADIUS;
  125.  
  126.   if((pnt = lnk->point.next) == NULL) return(NULL);
  127.   selected_pnt = NULL;
  128.  
  129.   while(pnt->next != NULL) {
  130.      r0 = pnt->dcx; s0 = pnt->dcy;
  131.      r1 = pnt->next->dcx; s1 = pnt->next->dcy;
  132.      d = (r1-r0)*(r1-r0) + (s1-s0)*(s1-s0);
  133.  
  134.      if(d != 0) {
  135.         t = ((float) ( (x-r0)*(r1-r0) + (y-s0)*(s1-s0) ))/((float) d);
  136.         if((t >= 0.0) && (t <= 1.0)) {
  137.  
  138.            xtemp = x - r0 - (int) (t*(r1-r0));
  139.            xtemp = (xtemp > 0) ? xtemp:-xtemp;
  140.  
  141.            ytemp = y - s0 - (int) (t*(s1-s0));
  142.            ytemp = (ytemp > 0) ? ytemp:-ytemp;
  143.  
  144.            if((xtemp <= x_diff) && (ytemp <= y_diff)) {
  145.               selected_pnt = pnt;
  146.               x_diff = xtemp;
  147.               y_diff = ytemp;
  148.              }
  149.           }
  150.        }
  151.      pnt = pnt->next;
  152.     }
  153.  
  154.   /* Special case if link is closed */
  155.   if(lnk->closed) {
  156.      r0 = pnt->dcx; s0 = pnt->dcy;
  157.      r1 = lnk->point.next->dcx; s1 = lnk->point.next->dcy;
  158.      d = (r1-r0)*(r1-r0) + (s1-s0)*(s1-s0);
  159.  
  160.      if(d != 0) {
  161.         t = ((float) ( (x-r0)*(r1-r0) + (y-s0)*(s1-s0) ))/((float) d);
  162.         if((t >= 0.0) && (t <= 1.0)) {
  163.  
  164.            xtemp = x - r0 - (int) (t*(r1-r0));
  165.            xtemp = (xtemp > 0) ? xtemp:-xtemp;
  166.  
  167.            ytemp = y - s0 - (int) (t*(s1-s0));
  168.            ytemp = (ytemp > 0) ? ytemp:-ytemp;
  169.  
  170.            if((xtemp <= x_diff) && (ytemp <= y_diff)) {
  171.               selected_pnt = pnt;
  172.               x_diff = xtemp;
  173.               y_diff = ytemp;
  174.              }
  175.           }
  176.        }
  177.     }
  178.  
  179.   return(selected_pnt);
  180. }
  181.  
  182.  
  183. LinkPointList *LinkFindPoint(gnrc,lnk,x,y)
  184.  
  185. LinkStatus *gnrc;
  186. LinkList *lnk;
  187. int x,y;
  188.  
  189. {
  190.   LinkPointList *pnt,*rtn;
  191.   int x_diff,y_diff,dcx,dcy;
  192.   int xtemp,ytemp;
  193.  
  194.   rtn = NULL;
  195.   pnt = lnk->point.next;
  196.   x_diff = LINK_X_HIT_RADIUS; y_diff = LINK_Y_HIT_RADIUS;
  197.  
  198.   while(pnt != NULL) {
  199.      dcx = pnt->dcx; dcy = pnt->dcy;
  200.      xtemp = (x > dcx) ? x-dcx:dcx-x; ytemp = (y > dcy) ? y-dcy:dcy-y;
  201.      if(xtemp <= x_diff && ytemp <= y_diff) {
  202.         rtn = pnt; x_diff = xtemp; y_diff = ytemp;
  203.        }
  204.      pnt = pnt->next;
  205.     }
  206.   return(rtn);
  207. }
  208.  
  209.  
  210. LinkAddPoint(gnrc,x,y)
  211. LinkStatus *gnrc; int x,y;
  212. /* Eventually: intelligently add points before, between, or after nodes */
  213.  
  214. {
  215.   LinkList *lnk;
  216.   int delta_x,delta_y;
  217.   LinkPointList *pnt;
  218.  
  219.   lnk = gnrc->current_link;
  220.   if(lnk == NULL) { /* Start a new link */ 
  221.      if((lnk = LinkCreateNewLink((VOID *) gnrc)) == NULL) return;
  222.      XClearWindow(dpy,gnrc->TopWindow);
  223.      ReDrawLinkTopWindow(gnrc);
  224.      LinkAddPointAfter(gnrc,lnk,x,y);
  225.      return;
  226.     }
  227.  
  228.   /* If point near first point, close link */
  229.   if((pnt = lnk->point.next) != NULL && !(lnk->closed) ) {
  230.      delta_x = x - pnt->dcx;  delta_x = (delta_x < 0) ? -delta_x:delta_x;
  231.      delta_y = y - pnt->dcy;  delta_y = (delta_y < 0) ? -delta_y:delta_y;
  232.      if(delta_x < LINK_X_HIT_RADIUS && delta_y < LINK_Y_HIT_RADIUS) {
  233.         LinkCloseCurrentLink((VOID *) gnrc);
  234.         return;
  235.        }
  236.     }
  237.  
  238.   /* else, if edge hit add to interior of edge */
  239.   if((pnt = LinkFindEdge(gnrc,lnk,x,y)) != NULL ) {
  240.      double param;
  241.      LinkPointList *nxt,*new;
  242.      LinkCrossingList *crssng;
  243.  
  244.      /* Compute param value of new point on edge */
  245.      if((nxt = pnt->next) == NULL) nxt = lnk->point.next;
  246.      delta_x = x - pnt->dcx;  delta_x = (delta_x < 0) ? -delta_x:delta_x;
  247.      delta_y = y - pnt->dcy;  delta_y = (delta_y < 0) ? -delta_y:delta_y;
  248.      if(delta_x > delta_y) 
  249.         param = (double) (x - pnt->dcx) / (double) (nxt->dcx - pnt->dcx);
  250.      else
  251.         param = (double) (y - pnt->dcy) / (double) (nxt->dcy - pnt->dcy);
  252.  
  253.      /* create new point */
  254.      new = (LinkPointList *) malloc(sizeof(LinkPointList));
  255.      if(new == NULL) {fprintf(stderr,"GULP! Out of space!\n"); return;}
  256.      new->x = pnt->x + param*(nxt->x - pnt->x);
  257.      new->y = pnt->y + param*(nxt->y - pnt->y);
  258.      new->z = -1.0;
  259.      new->next = pnt->next;
  260.      new->previous = pnt;
  261.  
  262.      if(pnt->next != NULL) pnt->next->previous = new;
  263.      pnt->next = new;
  264.      LinkComputePointDeviceCoords(gnrc,new); 
  265.      lnk->num ++;
  266.      
  267.      /* Fix crossing list */
  268.      crssng = pnt->crossing.next;
  269.      while(crssng != NULL) {
  270.         if(crssng->param > param) break;
  271.         crssng = crssng->next;
  272.        }
  273.      new->crossing.next = crssng;
  274.  
  275.      crssng = &(pnt->crossing);
  276.      while(crssng->next !=NULL) {
  277.         if(crssng->next->param > param) break;
  278.         crssng = crssng->next;
  279.         crssng->param /= param;
  280.        }
  281.      /* cut off crossing list at break point */
  282.      crssng->next = NULL;
  283.  
  284.      /* fix new crossing list */
  285.      crssng = new->crossing.next;
  286.      while(crssng != NULL) {
  287.         crssng->param = (crssng->param - param)/(1.0-param);
  288.         crssng->crossing->partner = new;
  289.         crssng = crssng->next;
  290.        }
  291.      XClearWindow(dpy,gnrc->TopWindow);
  292.      ReDrawLinkTopWindow(gnrc);
  293.      return;
  294.     }
  295.  
  296.   /* else, start new link if current closed */
  297.   if(lnk->closed) {
  298.      if((lnk = LinkCreateNewLink((VOID *) gnrc)) == NULL) return;
  299.      XClearWindow(dpy,gnrc->TopWindow);
  300.      ReDrawLinkTopWindow(gnrc);
  301.      LinkAddPointAfter(gnrc,lnk,x,y);
  302.      return;
  303.     }
  304.  
  305.   /* else, add to end of current link */  
  306.   LinkAddPointAfter(gnrc,lnk,x,y);
  307. }
  308.  
  309. LinkAddPointAfter(gnrc,lnk,x,y)
  310. LinkStatus *gnrc; LinkList *lnk; int x,y;
  311.  
  312. {
  313.   LinkPointList *pnt;
  314.  
  315.   if(lnk == NULL) {
  316.      LinkPrintMessage(gnrc,"No current link!");
  317.      return(0);
  318.     }
  319.   pnt = &(lnk->point);
  320.   while(pnt->next != NULL) pnt = pnt->next;
  321.   pnt->next = (LinkPointList *) malloc(sizeof(LinkPointList));
  322.   if(pnt->next == NULL) {
  323.      LinkPrintMessage(gnrc,"Out of memory!");
  324.      return(0);
  325.     }
  326.   pnt->next->previous = pnt;
  327.  
  328.   pnt = pnt->next;
  329.   pnt->dcx = x; pnt->dcy = y;
  330.   LinkComputePointWorldCoords(gnrc,pnt);
  331.   pnt->z = -1.0;
  332.   pnt->next = NULL;
  333.   pnt->crossing.next = NULL;
  334.  
  335.   lnk->num ++;
  336.   if(pnt->previous == &(lnk->point)) {  /* first point in link */
  337.      LinkDrawPoint(gnrc,lnk,pnt);
  338.     }
  339.   else { 
  340.     if(LinkComputeEdgeCrossings(gnrc,lnk,pnt->previous)){ /* crossings added */
  341.        XClearWindow(dpy,gnrc->TopWindow);
  342.        ReDrawLinkTopWindow(gnrc);
  343.       }
  344.     else {  /* Just draw edge */
  345.        LinkDrawPoint(gnrc,lnk,pnt);
  346.        LinkDrawEdge(gnrc,lnk,pnt->previous);
  347.       }
  348.    }
  349. }
  350.  
  351. LinkFreeEdgeCrossings(gnrc,lnk,pnt)
  352. LinkStatus *gnrc; LinkList *lnk; LinkPointList *pnt;
  353. {
  354.   LinkCrossingList *crssng,*tmp;
  355.  
  356.   if(pnt == NULL) return;
  357.   /* Free crossing data of pnt and crossing partners */
  358.   crssng = pnt->crossing.next;
  359.   pnt->crossing.next = NULL;
  360.   while(crssng != NULL) {
  361.      tmp = crssng->next;
  362.      LinkFreeCrossing(gnrc,crssng->partner,crssng->crossing);
  363.      free(crssng);
  364.      crssng = tmp;
  365.     }
  366. }
  367.  
  368. LinkDeleteAll(gnrc)
  369. LinkStatus *gnrc; 
  370. {
  371.   LinkList *lnk,*tmp;
  372.   lnk = gnrc->link.next;
  373.   while(lnk != NULL) {
  374.      tmp = lnk->next;
  375.      LinkDeleteLink(gnrc,lnk);
  376.      lnk = tmp;
  377.     }
  378.   gnrc->num = 0;
  379. }
  380.  
  381. LinkDeleteLink(gnrc,lnk)
  382. LinkStatus *gnrc; LinkList *lnk;
  383. {
  384.   LinkPointList *pnt,*tmp;
  385.   LinkList *lnk_ptr;
  386.   
  387.   if(lnk == NULL) return;
  388.  
  389.   if(gnrc->current_link == lnk) {  /* Change current link */
  390.      if(gnrc->link.next != lnk) 
  391.         gnrc->current_link = gnrc->link.next;
  392.      else
  393.         gnrc->current_link = lnk->next;
  394.     }
  395.  
  396.   /* remove crossings and points */
  397.   pnt = lnk->point.next;
  398.   while(pnt != NULL) {
  399.      LinkFreeEdgeCrossings(gnrc,lnk,pnt);
  400.      pnt = pnt->next; 
  401.     }
  402.   pnt = lnk->point.next;
  403.   while(pnt != NULL) {
  404.      tmp = pnt->next;
  405.      free(pnt);
  406.      pnt = tmp;
  407.     }
  408.  
  409.   /* remove from list of links */
  410.   lnk_ptr = &(gnrc->link);
  411.   while(lnk_ptr->next != NULL) {
  412.      if(lnk_ptr->next == lnk) {
  413.         lnk_ptr->next = lnk->next;
  414.         break;
  415.        }
  416.      lnk_ptr = lnk_ptr->next;
  417.     }
  418.   free(lnk);
  419.   gnrc->num --;
  420. }
  421.  
  422. LinkDeletePoint(gnrc,lnk,pnt)
  423. LinkStatus *gnrc;LinkList *lnk;LinkPointList *pnt;
  424. /* Routine deletes pnt and recomputes crossings for pnt->previous */
  425. {
  426.   LinkPointList *prev_pnt,*tmp_pnt;
  427.  
  428.   if(pnt == NULL) return;
  429.   if(lnk->closed && lnk->num < 4) {
  430.      LinkPrintMessage(gnrc,"Too few points on closed link to delete!");
  431.      return;
  432.     }
  433.  
  434.   /* Free crossings on pnt and pnt->previous */
  435.   LinkFreeEdgeCrossings(gnrc,lnk,pnt);
  436.   prev_pnt = pnt->previous;
  437.   if(lnk->closed && prev_pnt == &(lnk->point)) {
  438.      /* If link is closed recompute crossing from last point */
  439.      prev_pnt = &(lnk->point);
  440.      while(prev_pnt->next != NULL) prev_pnt = prev_pnt->next;
  441.     }
  442.   if(prev_pnt != &(lnk->point))
  443.      LinkFreeEdgeCrossings(gnrc,lnk,prev_pnt);
  444.   
  445.  
  446.   /* remove pnt from list */
  447.   tmp_pnt = pnt->previous;
  448.   tmp_pnt->next = pnt->next;
  449.   if(pnt->next != NULL) pnt->next->previous = tmp_pnt;
  450.   free(pnt); 
  451.   lnk->num--;
  452.  
  453.   /* Recompute crossing for prev_pnt */
  454.   if(prev_pnt != &(lnk->point))
  455.      LinkComputeEdgeCrossings(gnrc,lnk,prev_pnt);
  456. }
  457.  
  458. LinkReComputeEdgeCrossings(gnrc,lnk,pnt)
  459. LinkStatus *gnrc;LinkList *lnk;LinkPointList *pnt;
  460.  
  461. /* Routine removes all the crossing structures from pnt and all */
  462. /* corresponding crossings on partners and recomputes crossings for pnt. */
  463. /* Over-under relationships are maintained. */ 
  464. {
  465.   LinkCrossingList *crssng,*old_crssng,*tmp;
  466.  
  467.   if(pnt == NULL) return;
  468.   old_crssng = crssng = pnt->crossing.next;  /* Save old list */
  469.   pnt->crossing.next = NULL;
  470.   while(crssng != NULL) {
  471.      LinkFreeCrossing(gnrc,crssng->partner,crssng->crossing);
  472.      crssng = crssng->next;
  473.     }
  474.   LinkComputeEdgeCrossings(gnrc,lnk,pnt);
  475.  
  476.   /* Restore over under relationships */
  477.   crssng = pnt->crossing.next;
  478.   while(crssng != NULL) {
  479.      tmp = old_crssng;
  480.      while(tmp != NULL) {
  481.         if(tmp->partner == crssng->partner) { /* restore over-under */
  482.            if(tmp->z > 0.0) {
  483.               crssng->z = 1.0; crssng->crossing->z = -1.0;
  484.              }
  485.            else {
  486.               crssng->z = -1.0; crssng->crossing->z = 1.0;
  487.              }
  488.           }
  489.         tmp = tmp->next;
  490.        }
  491.      crssng = crssng->next;
  492.     }
  493.  
  494.   /* Free old crossing list */
  495.   crssng = old_crssng;
  496.   while(crssng != NULL) {
  497.      tmp = crssng->next;
  498.      free(crssng);
  499.      crssng = tmp;
  500.     } 
  501. }
  502.  
  503. LinkFreeCrossing(gnrc,pnt,crssng)
  504. LinkStatus *gnrc; LinkPointList *pnt; LinkCrossingList *crssng;
  505. /* Routine removes crssng from the corssing list of pnt */
  506. {
  507.   LinkCrossingList *tmp;
  508.  
  509.   if(pnt == NULL) return;
  510.   tmp = &(pnt->crossing);
  511.   while(tmp->next != NULL) {
  512.      if(tmp->next == crssng) {
  513.         tmp->next = crssng->next;
  514.         free(crssng);
  515.         break;
  516.        }
  517.      tmp = tmp->next;
  518.     }
  519. }
  520.  
  521. LinkComputeEdgeCrossings(gnrc,lnk,pnt)
  522. LinkStatus *gnrc;LinkList *lnk;LinkPointList *pnt;
  523. /* routine computes all crossings between edge beginning with pnt (on */
  524. /* link lnk) and all other edges on all other links */
  525. /* returns the number of crossings inserted */
  526. /* Note: when reading links ove existing links, this routine is */
  527. /* used  when lnk is not actually on the list attached to gnrc! */
  528.  
  529. {
  530.   LinkList *tmp_lnk;
  531.   LinkPointList *tmp_pnt;
  532.   LinkCrossingList crossing;
  533.   double param,tmp_param;
  534.   int total;
  535.  
  536.   if(pnt == NULL) return(0);
  537.  
  538.   tmp_lnk = gnrc->link.next;
  539.   total = 0;
  540.   while(tmp_lnk != NULL) {
  541.      tmp_pnt = tmp_lnk->point.next;
  542.      while(tmp_pnt != NULL) {
  543.         if(LinkEdgeCrossEdge(gnrc,lnk,pnt,tmp_lnk,tmp_pnt,&crossing,
  544.                                ¶m,&tmp_param)) {
  545.             LinkInsertCrossing(gnrc,lnk,pnt,tmp_lnk,tmp_pnt,&crossing,
  546.                                param,tmp_param);
  547.             total++;
  548.            }
  549.         tmp_pnt = tmp_pnt->next;
  550.        }
  551.      tmp_lnk = tmp_lnk->next;
  552.     }
  553.   return(total);
  554. }
  555.  
  556. LinkInsertCrossing(gnrc,lnk1,pnt1,lnk2,pnt2,crossing,param1,param2)
  557.  
  558. LinkStatus *gnrc; LinkList *lnk1,*lnk2; LinkPointList *pnt1,*pnt2;
  559. LinkCrossingList *crossing; double param1, param2;
  560.  
  561. /* Routine places crossing in the crossing lists of pnt1 and pnt2, in the */
  562. /* position determined by param1 and param2 .  crossing on pnt1 goes on top*/
  563.  
  564. {
  565.   LinkCrossingList *tmp,*nxt;
  566.   LinkCrossingList *crssng1,*crssng2;
  567.  
  568.   tmp = &(pnt1->crossing);
  569.   while(tmp->next != NULL) {
  570.       if(tmp->next->param > param1) break; 
  571.       tmp = tmp->next;
  572.      }
  573.   nxt = tmp->next;
  574.   tmp->next = (LinkCrossingList *) malloc(sizeof(LinkCrossingList));
  575.   if(tmp->next == NULL) {
  576.      fprintf(stderr,"PANIC! Cannot allocate crossing node!");
  577.      return(0);
  578.     }
  579.   crssng1 = tmp->next;
  580.   crssng1->next = nxt;
  581.   crssng1->partner = pnt2;
  582.   crssng1->param = param1;
  583.   crssng1->x = crossing->x; crssng1->y = crossing->y; crssng1->z = 1.0;
  584.   crssng1->dcx = crossing->dcx; crssng1->dcy = crossing->dcy;
  585.  
  586.   tmp = &(pnt2->crossing);
  587.   while(tmp->next != NULL) {
  588.       if(tmp->next->param > param2) break;
  589.       tmp = tmp->next;
  590.      }
  591.   nxt = tmp->next;
  592.   tmp->next = (LinkCrossingList *) malloc(sizeof(LinkCrossingList));
  593.   if(tmp->next == NULL) {
  594.      fprintf(stderr,"PANIC! Cannot allocate crossing node!");
  595.      return(0);
  596.     }
  597.   crssng2 = tmp->next;
  598.   crssng2->next = nxt;
  599.   crssng2->partner = pnt1;
  600.   crssng2->param = param2;
  601.   crssng2->x = crossing->x; crssng2->y = crossing->y; crssng2->z = -1.0;
  602.   crssng2->dcx = crossing->dcx; crssng2->dcy = crossing->dcy;
  603.  
  604.   /* cross reference crossings */
  605.   crssng1->crossing = crssng2;
  606.   crssng2->crossing = crssng1;
  607. }
  608.  
  609.  
  610. LinkEdgeCrossEdge(gnrc,lnk1,pnt1,lnk2,pnt2,crossing,param1,param2)
  611.  
  612. LinkStatus *gnrc; LinkList *lnk1,*lnk2; LinkPointList *pnt1,*pnt2;
  613. LinkCrossingList *crossing; double *param1,*param2;
  614.  
  615. /* Routine returns 1 if a crossing occurs in the xy projections */
  616. /* 0 if not.  If yes, the crossing point is returned in crossing */
  617. {
  618.   double coeff[2][3];
  619.   LinkPointList sample,*nxt1,*nxt2;
  620.   int success;
  621.  
  622.   if(pnt1 == pnt2) return(0); 
  623.   if(pnt1->next == NULL && lnk1->closed == LINK_NO) return(0);
  624.   if(pnt2->next == NULL && lnk2->closed == LINK_NO) return(0);
  625.  
  626.   success = 0;
  627.   if((nxt1 = pnt1->next) == NULL) nxt1 = lnk1->point.next;
  628.   if((nxt2 = pnt2->next) == NULL) nxt2 = lnk2->point.next;
  629.   if(pnt1 == nxt2 || pnt2 == nxt1) return(0);
  630.  
  631.   coeff[0][0] = nxt1->x - pnt1->x; coeff[0][1] = pnt2->x - nxt2->x; 
  632.   coeff[0][2] = pnt2->x - pnt1->x;
  633.   coeff[1][0] = nxt1->y - pnt1->y; coeff[1][1] = pnt2->y - nxt2->y; 
  634.   coeff[1][2] = pnt2->y - pnt1->y;
  635.   if(SolveTwoByTwo(coeff,param1,param2)) {
  636.      if(0.0 < *param1 && *param1 < 1.0 && 0.0 < *param2 && *param2 < 1.0) {
  637.         sample.x = pnt1->x + *param1 * (nxt1->x-pnt1->x);
  638.         sample.y = pnt1->y + *param1 * (nxt1->y-pnt1->y);
  639.         LinkComputePointDeviceCoords(gnrc,&sample);
  640.         crossing->x = sample.x; crossing->y = sample.y;
  641.         crossing->dcx = sample.dcx;  crossing->dcy = sample.dcy;
  642.         success = 1; 
  643.        }
  644.     }
  645.   return(success);
  646. }
  647. LinkClearData(gnrc)
  648.  
  649. LinkStatus *gnrc;
  650.  
  651. {
  652.   LinkList *lnk,*tmp_lnk;
  653.   LinkPointList *pnt,*tmp_pnt;
  654.  
  655.   lnk = gnrc->link.next;
  656.   while(lnk != NULL) {
  657.      tmp_lnk = lnk->next;
  658.      pnt = lnk->point.next;
  659.         while(pnt != NULL) {
  660.         tmp_pnt = pnt->next;
  661.         free(pnt);
  662.         pnt = tmp_pnt;
  663.        }
  664.      free(lnk);
  665.      lnk = tmp_lnk;
  666.     }
  667.   gnrc->link.next = NULL;
  668.   gnrc->choice[0] = LINK_NO_CHOICE;
  669.  
  670.   XClearWindow(dpy,gnrc->TopWindow);
  671.   ReDrawLinkTopWindow(gnrc);
  672. }
  673.  
  674. LinkReverseArrows(gnrc,lnk)
  675. LinkStatus *gnrc; LinkList *lnk;
  676. /* Routine reverses the order of points in the linked list */
  677. /* NOTE:  this routine is rather complicated due to the way */
  678. /* crossing information is stored.  An edge is implicitly referenced */
  679. /* as its first vertex, and crossing data for the edge is stored on a list at */
  680. /* that vertex.  When reversing arrows the point representing the */
  681. /* edge changes, and so all the crossing data must be transfered, */
  682. /* references updated, crossing param changed, and the list of crossings */
  683. /* themselves reversed! */
  684. {
  685.   LinkPointList *pnt,*tmp,*nxt_pnt;
  686.   LinkCrossingList *crssng,*this_crssng,*nxt_crssng,*prev_crssng;
  687.   LinkCrossingList *tmp_crssng;
  688.  
  689.   if(lnk == NULL) return;
  690.  
  691.   /* reverse point list */
  692.  
  693.   /* Do first point */
  694.   if((pnt = lnk->point.next) == NULL) return; 
  695.  
  696.   /* save crossinglist for while loop*/
  697.   crssng = pnt->crossing.next;
  698.  
  699.   if(lnk->closed) {  /* assign crossing list of last point to pnt */
  700.      tmp = pnt;
  701.      while(tmp->next != NULL) tmp = tmp->next;
  702.      pnt->crossing.next = tmp->crossing.next;
  703.  
  704.      /* fix list: change param and reverse crossing order */
  705.      if((this_crssng = pnt->crossing.next) != NULL) {
  706.         this_crssng->param = 1.0 - this_crssng->param;
  707.         /* fix reference to this_crssng pnt */
  708.         this_crssng->crossing->partner = pnt;
  709.  
  710.         if((nxt_crssng = this_crssng->next) != NULL) {
  711.            this_crssng->next = NULL;
  712.            prev_crssng = this_crssng;
  713.            this_crssng = nxt_crssng;
  714.            while(this_crssng != NULL) {
  715.               this_crssng->param = 1.0 - this_crssng->param;
  716.               /* fix reference to this_crssng pnt */
  717.               this_crssng->crossing->partner = pnt;
  718.  
  719.               nxt_crssng = this_crssng->next;
  720.               this_crssng->next = prev_crssng;
  721.               prev_crssng = this_crssng;
  722.               this_crssng = nxt_crssng;
  723.  
  724.              }
  725.            pnt->crossing.next = prev_crssng;
  726.  
  727.           }
  728.        }
  729.     }
  730.   else {   /* No crossing list at this point */
  731.      pnt->crossing.next = NULL;
  732.     }
  733.  
  734.   nxt_pnt = pnt->next;
  735.   pnt->previous = pnt->next;
  736.   pnt->next = NULL;
  737.  
  738.   /* Remaining points : nxt_pnt is next point after current pnt*/
  739.   /* crssng is the previous point's crossing list */
  740.  
  741.   while(nxt_pnt != NULL) {
  742.      pnt = nxt_pnt;
  743.      nxt_pnt = nxt_pnt->next; 
  744.      /* re-asssign crossing lists */
  745.      tmp_crssng = pnt->crossing.next;
  746.      pnt->crossing.next = crssng;
  747.  
  748.      /* fix list: change param and reverse crossing order */
  749.      if((this_crssng = pnt->crossing.next) != NULL) {
  750.         this_crssng->param = 1.0 - this_crssng->param;
  751.         /* fix reference to this_crssng pnt */
  752.         this_crssng->crossing->partner = pnt;
  753.  
  754.         if((nxt_crssng = this_crssng->next) != NULL) {
  755.            this_crssng->next = NULL;
  756.            prev_crssng = this_crssng;
  757.            this_crssng = nxt_crssng;
  758.            while(this_crssng != NULL) {
  759.               this_crssng->param = 1.0 - this_crssng->param;
  760.               /* fix reference to this_crssng pnt */
  761.               this_crssng->crossing->partner = pnt;
  762.  
  763.               nxt_crssng = this_crssng->next;
  764.               this_crssng->next = prev_crssng;
  765.               prev_crssng = this_crssng;
  766.               this_crssng = nxt_crssng;
  767.  
  768.              }
  769.            pnt->crossing.next = prev_crssng;
  770.  
  771.           }
  772.        }
  773.  
  774.      crssng = tmp_crssng;
  775.  
  776.      tmp = pnt->next;
  777.      pnt->next = pnt->previous;
  778.      pnt->previous = tmp;
  779.     }
  780.   /* Fix last point */
  781.   pnt->previous = &(lnk->point);
  782.   lnk->point.next = pnt;
  783.   
  784. }
  785.  
  786. LinkJoinLinks(gnrc,first,second)
  787. LinkStatus *gnrc; LinkList *first,*second;
  788. {
  789.   LinkPointList *pnt;
  790.   LinkList *lnk;
  791.  
  792.   if(first->closed || second->closed) return;
  793.   if(second->point.next == NULL) return;
  794.  
  795.   pnt = &(first->point);
  796.   while(pnt->next != NULL) pnt = pnt->next;
  797.  
  798.   /* Attach second to first */
  799.   pnt->next = second->point.next;
  800.   second->point.next->previous = pnt;
  801.  
  802.   /* remove second from list of links */
  803.   lnk = &(gnrc->link);
  804.   while(lnk->next != second) lnk = lnk->next; 
  805.   lnk->next = second->next;
  806.   free(second);
  807.  
  808.   /* compute new crossings */
  809.   LinkComputeEdgeCrossings(gnrc,first,pnt);
  810. }
  811.  
  812.